import utils.TreeNode;

import java.util.LinkedList;
import java.util.Queue;

/**
 * @Author ZhangCuirong
 * @Date 2025/9/5 8:25
 * @description:
 */
public class Solution662 {
    public static class Pair {
        TreeNode node;
        int index;

        public Pair(TreeNode node, int index) {
            this.node = node;
            this.index = index;
        }
    }

    public int widthOfBinaryTree(TreeNode root) {
        if (root == null) {
            return 0;
        }
        int maxWidth = 1;
        Queue<Pair> queue = new LinkedList<>();
        int index = 0;
        queue.add(new Pair(root, index));
        while (!queue.isEmpty()) {
            int size = queue.size();
            Pair first = null;
            Pair second = null;
            for (int i = 0; i < size; i++) {
                Pair pair = queue.poll();
                if (i == 0) {
                    first = pair;
                }
                if (i == size - 1) {
                    second = pair;
                }
                TreeNode node = pair.node;
                index++;
                if (node.left != null) {
                    queue.add(new Pair(node.left, 2 * pair.index));
                }
                index++;
                if (node.right != null) {
                    queue.add(new Pair(node.right, 2 * pair.index + 1));
                }
            }
            if (first != null && second != null) {
                maxWidth = Math.max(maxWidth, second.index - first.index + 1);
            }
        }
        return maxWidth;
    }

    public static void main(String[] args) {
        Solution662 solution = new Solution662();
        TreeNode root = TreeNode.buildTree(new int[]{1, 3, 2, 5, 3, -1, 9}, -1);
        System.out.println(solution.widthOfBinaryTree(root));
    }
}
